package com.jack.leetcode.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 电话号码的字母组合 {

    private static Map<Integer, Character[]> map = new HashMap<>();

    static {
        map.put(2, new Character[]{'a', 'b', 'c'});
        map.put(3, new Character[]{'d', 'e', 'f'});
        map.put(4, new Character[]{'g', 'h', 'i'});
        map.put(5, new Character[]{'j', 'k', 'l'});
        map.put(6, new Character[]{'m', 'n', 'o'});
        map.put(7, new Character[]{'p', 'q', 'r', 's'});
        map.put(8, new Character[]{'t', 'u', 'v'});
        map.put(9, new Character[]{'w', 'x', 'y', 'z'});
    }

    public static void main(String[] args) {
        String digits = "234";
        List<String> result = letterCombinations(digits);
        result.forEach(r -> System.out.print(r + " "));
    }

    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if (digits == null || digits.length() == 0) {
            return result;
        }
        Character[] characters = map.get(digits.charAt(0) - '0');
        for (int i = 0; i < characters.length; i++) {
            result.add(characters[i].toString());
        }
        rev(result, digits, 1);
        return result;
    }

    private static void rev(List<String> result, String s, int i) {
        if (i >= s.length()) {
            return;
        }
        int n = result.size();
        Character[] characters = map.get(s.charAt(i) - '0');
        for (int k = 0; k < n; k++) {
            for (int l = 0; l < characters.length; l++) {
                result.add(result.get(k) + characters[l]);
            }
        }
        result.removeIf(r -> r.length() <= i);
        rev(result, s, i + 1);
    }
}
